package slidingwindow

import (
	"container/list"
	"fmt"
)

// 1856. 子数组最小乘积的最大值
//一个数组的 最小乘积定义为这个数组中 最小值乘以数组的 和。
//比方说，数组[3,2,5]（最小值是2）的最小乘积为2 * (3+2+5) = 2 * 10 = 20。
// 给你一个正整数数组nums，请你返回nums任意非空子数组的最小乘积的最大值。由于答案可能很大，请你返回答案对109 + 7取余的结果。
// 请注意，最小乘积的最大值考虑的是取余操作 之前的结果。题目保证最小乘积的最大值在 不取余 的情况下可以用 64 位有符号整数保存。
// 子数组定义为一个数组的 连续部分。

// 示例：
// 输入：nums = [1,2,3,2]
// 输出：14
// 解释：最小乘积的最大值由子数组 [2,3,2] （最小值是 2）得到。
// 2 * (2+3+2) = 2 * 7 = 14 。

func GetSubsMinMultiMax(nums []int) int {
	var ans int
	// 位置信息 如：[0:[-1, 3]] nums[0] 位置左边比他小的值没有， 右边比他小的值的index为3
	posInfo := make([][]int, len(nums))
	for i:=0; i<len(posInfo); i++ {
		posInfo[i] = make([]int, 2)
	}

	monotStack := list.New()

	for i, num := range nums {
		// 长度大于0的时候，进入时如果最后一个值小于数组列表的最后一个，需要弹出之前的内容并且记录
		for monotStack.Len() > 0 && nums[monotStack.Back().Value.([]int)[0]] > num {
			popIs := monotStack.Remove(monotStack.Back()).([]int)
			leftLessIndex := -1
			if monotStack.Len() > 0 {
				beforeIs := monotStack.Back().Value.([]int)
				leftLessIndex = beforeIs[len(beforeIs)-1]
			}
			for _, v := range popIs {
				posInfo[v][0] = leftLessIndex
				posInfo[v][1] = i
			}
		}
		if monotStack.Len() > 0 && nums[monotStack.Back().Value.([]int)[0]] == num {
			popIs := monotStack.Remove(monotStack.Back()).([]int)
			monotStack.PushBack(append(popIs, i))
		} else {
			monotStack.PushBack([]int{i})
		}
	}
	for monotStack.Len() > 0 {
		curArr := monotStack.Remove(monotStack.Back()).([]int)
		for _, v := range curArr {
			leftLessIndex := -1
			if monotStack.Len() > 0 {
				beforeIs := monotStack.Back().Value.([]int)
				leftLessIndex = beforeIs[len(beforeIs)-1]
			}
			posInfo[v][0] = leftLessIndex
			posInfo[v][1] = -1
		}
	}
	fmt.Println(posInfo)
	return ans
}


